package 力扣面试经典150;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-16
 * Time:17:07
 */

/**
 * 力扣面试经典150:39. 组合总和
 * 中等
 * 相关标签
 * 相关企业 
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * 示例 1：
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 */
public class combinationSum {

    List<List<Integer>> ans;
    List<Integer> res;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ans = new ArrayList<>();
        res = new ArrayList<>();

        if(candidates.length == 0)return ans;
        dfs(candidates,target,0,0);
        return ans;

    }
    public void dfs(int[] candidates,int target,int depth,int sum){
        if(depth == candidates.length || sum + candidates[depth] > target){
            return;
        }
        if(sum == target){
            ans.add(new ArrayList<>(res));
            return;
        }
        sum += candidates[depth];
        res.add(candidates[depth]);
        dfs(candidates,target,depth,sum);
        sum -= candidates[depth];
        res.remove(res.size() - 1);
        dfs(candidates,target,depth + 1,sum);

    }
}
